package org.example.leetcode;
import javax.print.attribute.standard.NumberUp;
import java.util.*;
/**
 * @version 1.0.0
 * @author: lynn
 * @description:  四数之和
 * @date: 2021/7/26 18:44
 */
public class LC18 {

    public static void main(String[] args) {
        LC18 lc = new LC18();
        int[] nums = {1, 0, -1, 0, -2, 2};
        System.out.println(lc.fourSum(nums, 0));
    }

    //回溯算法求解
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length == 0 || nums == null) return new ArrayList<>(res);
        List<Integer> curList = new ArrayList<>();
        Arrays.sort(nums);
        backTrack(nums, 0, res, curList, target);
        return new ArrayList<>(res);
    }



    private void backTrack(int[] nums, int start, List<List<Integer>> res, List<Integer> curList, int target) {
        if (start >= nums.length) {
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if(i>start && nums[i]==nums[i-1]) continue;
            curList.add(nums[i]);
            if(curList.size()==4 &&  (curList.get(0) + curList.get(1) + curList.get(2) + curList.get(3) == target)){
                res.add(new ArrayList<>(curList));
            }
            backTrack(nums, i + 1, res, curList, target);
            curList.remove(curList.size() - 1);
        }
    }
}

